ABC153 D - Caracal vs Monster

https://atcoder.jp/contests/abc153/tasks/abc153_d

提出

TLE

code: python

import math

h = int(input())

ans = 0

def attack(n):

global ans

ans += 1

if (n == 1):

pass

else:

attack(math.floor(n / 2))

attack(h)

print(ans)

解答

code: python

import math

h = int(input())

def attack(n):

if (n == 1):

return 1

# 2 体に分裂するのに　+1、n/2 を 2 体倒すのに attack(n / 2) *2

return 1 + attack(math.floor(n / 2))*2

print(attack(h))

提出

code: python

h = int(input())

# def attack(n, ans):

# ans += 1

# if n == 1:

# print(ans)

# exit()

# else:

# attack(n//2, ans)

# 再帰は不可能

# 事前に計算できないか dp <- そもそもこれをどう計算するか

# 2 => 1, 1 => 0, 0

# 3 => 1, 1 => 0, 0

# 4 => 2, 2 => 1, 1, 1, 1 => 0, 0

# 6 => 3, 3

# 7 => 3, 3

# 8 => 4, 4

# 2 => 3

# 3 => 3

# 4 => 7

# 5 => 7

# 下から順では無理っぽい

dp = 0 * 100

dp2 = 3

dp3 = 3

dp4 = 1 + dp4//2*2

# H = 1000000000000

# dp1000000000000 = 1 + dp500000000000*2 = 1 + (1 + dp500000000000//2*2)*2

for i in range(500000000000):

print(i*2)

メモ

再帰ができてる